#include <bits/stdc++.h>

using namespace std;

// 实现LRU结构
// 测试链接 : https://leetcode.cn/problems/lru-cache/

// 自己实现双向链表
class Node
{
public:
    int key, val;
    Node* prev;
    Node* next;

    Node(int k = 0, int v = 0)
    {
        key = k;
        val = v;
    }
};

class List
{
public:
    // 申请哨兵位头结点的内存
    List() : dummy(new Node())
    {
        dummy->next = dummy;
        dummy->prev = dummy;
    }

    // 在链表的末尾添加新节点
    void addNode(Node* newNode)
    {
        Node* tail = dummy->prev;
        // dummy ... tail newNode
        tail->next = newNode;
        newNode->prev = tail;
        dummy->prev = newNode;
        newNode->next = dummy;
    }

    // 将节点移动到链表的末尾
    void moveNodeToTail(Node* node)
    {
        Node* tail = dummy->prev;
        Node* head =dummy->next;
        if(tail == node) return; // 该节点本来就在链表的末尾
        // dummy ... node ... tail
        // node 的前后节点进行连接
        // node 是不是第一个节点都能够保证正确性
        node->prev->next = node->next;
        node->next->prev = node->prev;
        // 将 node 与 tail 和 dummy 进行连接
        tail->next = node;
        node->prev = tail;
        dummy->prev = node;
        node->next = dummy;
    }

    Node* removeHead()
    {
        Node* head = dummy->next;
        if(head == dummy) return nullptr; // 一个节点都没有
        // dummy head ... tail
        // 是否只有一个节点都能够保证正确性
        dummy->next = head->next;
        head->next->prev = dummy;
        return head; // 返回要删除的节点
    }

private:
    Node* dummy; // 哨兵位头结点
};

class LRUCache
{
private:
    unordered_map<int, Node*> m;
    List l; // 带有哨兵位的头结点
    int cap;

public:
    LRUCache(int capacity) 
        : cap(capacity)
    {}
    
    // 链表的头部是最近最少使用的数据
    int get(int key) 
    {
        if(m.count(key))
        {   
            Node* node = m[key];
            l.moveNodeToTail(node);
            return node->val;
        }
        return -1;
    }
    
    void put(int key, int value) 
    {
        if(m.count(key))
        {
            Node* node = m[key];
            node->val = value;
            l.moveNodeToTail(node);
        }
        else
        {
            if(m.size() == cap)
            {
                Node* delNode = l.removeHead();
                m.erase(delNode->key);
                delete delNode; // 释放内存
            }
            Node* newNode = new Node(key, value);
            l.addNode(newNode); // 将新节点添加到链表的末尾
            m[key] = newNode;
        }
    }
};


// 使用标准库的双向链表
class LRUCache
{
private:

    using ListIterator = list<pair<int, int>>::iterator;
    // 哈希表做到查找和更新的时间复杂度为 O(1)
    // 哈希表中存的是 key 和 key 在双向链表中的位置(迭代器)
    unordered_map<int, ListIterator> m;
    // LRU 假设链表尾部的数据是最近最少用的数据
    // 双向链表中存储的是键值对 pair
    list<pair<int, int>> l;
    int cap; // 记录容量

public:
    LRUCache(int capacity) 
        : cap(capacity)
    {}
    
    // 链表开头的 key 值是最近使用过的
    int get(int key) 
    {
        auto ret = m.find(key);
        if(ret == m.end()) return -1; // key 值不存在
        // 更新 key 的位置
        // 方法 1.erase + push_front 更新迭代器，原迭代器失效
        // 方法 2.splice 将节点转移到头部
        ListIterator it = ret->second; 
        l.splice(l.begin(), l, it); // 将 key-value 移动到链表的开头
        return it->second;
    }
    
    void put(int key, int value) 
    {
        // 1.新增 2.更新
        auto ret = m.find(key);
        if(ret == m.end()) // 哈希表中没有 key
        {
            // 满了，先删除最近最少用的数据
            if(m.size() == cap)
            {
                pair<int, int> data = l.back();
                m.erase(data.first);
                l.pop_back();
            }
            l.push_front({key, value});
            m[key] = l.begin();
        }
        else
        {
            // 更新 key 对应的值
            ListIterator it = ret->second;
            it->second = value;
            // 更新 key 对应值的位置
            // 方法 1.erase + push_front 更新迭代器，原迭代器失效
            // 方法 2.splice 将节点转移到头部
            l.splice(l.begin(), l, it);
        }
    }
};